|
In computability theory a numbering is the assignment of natural numbers to a set of objects such as functions, rational numbers, graphs, or words in some language. A numbering can be used to transfer the idea of computability and related concepts, which are originally defined on the natural numbers using computable functions, to these different types of objects. Common examples of numberings include Gödel numberings in first-order logic and admissible numberings of the set of partial computable functions. == Definition and examples == A numbering of a set is a surjective partial function from to ''S'' (Ershov 1999:477). The value of a numbering ν at a number ''i'' (if defined) is often written ν'i'' instead of the usual . For example, the set of all finite subsets of has a numbering γ in which and (Ershov 1999:477). As a second example, a fixed Gödel numbering of the computable partial functions can be used to define a numbering ''W'' of the recursively enumerable sets, by letting by ''W''(''i'') be the domain of φ''i''. 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「Numbering (computability theory)」の詳細全文を読む スポンサード リンク
|